package com.example.demo.leetcode.top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Linked_两数相加 {


    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        Stack<Integer> stack1= new Stack<>();
        Stack<Integer> stack2= new Stack<>();
        Stack<Integer> stack3= new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2=l2.next;
        }

        int a=0,b=0;
        int len1=stack1.size(),len2=stack2.size();
        int max = len1 > len2 ? len1 : len2;
        int [] arr = new int[max+1];
        for(int i=len1-1,j=len2-1;i>=0 || j>=0;i--,j--){
            if(i>j){
                arr[i]=stack1.pop();
                j++;
            } else if(i<j){
                arr[j]=stack2.pop();
                i++;
            } else if(i==j){
                int end = stack1.pop() + stack2.pop();
                addArr(arr,end,i);
            }
        }
        System.out.println(arr);
        return digui(arr,0);
    }

    public static void addArr(int [] arr ,int end,int i){
        if(end<10){
            arr[i]=end;
        }else{
            int mo = end % 10;
            end = end/10;
            arr[i] = mo;
            int newEnd = arr[i+1] + end;
            addArr(arr,newEnd,i+1);
        }
    }

    public static ListNode digui(int [] arr,int start){
        if(arr.length==start){
            return null;
        }
        //排除最后一个是0的影响
        if(arr.length-1 == start && arr[arr.length-1]==0){
            return null;
        }
        int c = arr[start];
        ListNode node = new ListNode(c);
        node.next = digui(arr,start+1);
        return node;
    }

    public static ListNode createList(List<Integer> list){
        if(list.size()==0){
            return null;
        }
        Integer remove = list.remove(0);
        ListNode node = new ListNode(remove);
        node.next = createList(list);
        return node;
    }

    public static void main(String[] args) {
        Integer [] arr1 = {9,9,9,9,9,9,9};
        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(arr1));
        Integer [] arr2 = {9,9,9,9};
        List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(arr2));
        addTwoNumbers(createList(list1),createList(list2));
    }


}
